﻿using System;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Ink;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;
using System.Collections.Generic;

namespace IKE_painter
{
    public class Floyd_Warshall
    {
        public int[,] D;
        public Node[,] P;

        public Node[] nodes;
        public Edge[] edges;

        /***** inicializace *****/
        public Floyd_Warshall(Node[] Nodes, Edge[] Edges)
        {
            nodes = Nodes;
            edges = Edges;
        }

        /***** inicializace délek *****/
        private int[,] initializeWeight()
        {
            int[,] Weight = new int[nodes.Length, nodes.Length];
            for (int i = 0; i < nodes.Length; i++)
                for (int j = 0; j < nodes.Length; j++)
                {
                    if (i == j) Weight[i, j] = 0;
                    else Weight[i, j] = int.MaxValue;
                }

            foreach (Edge e in edges)
            {
                Weight[getID(((Node)e.From).Name), getID(((Node)e.To).Name)] = e.Weight;
                Weight[getID(((Node)e.To).Name), getID(((Node)e.From).Name)] = e.Weight;
            }

            return Weight;
        }

        /***** vrátí ID termu(pořadí uzlu) podle názvu termu(TermID) *****/
        public int getID(int Name)
        {
            for (int i = 0; i < nodes.Length; i++)
                if (nodes[i].Name == Name)
                    return i;
            return -1;

        }


        /***** naplní matici délkami pro každý uzel *****/
        public void calcShortestPaths()
        {
            D = initializeWeight();
            P = new Node[nodes.Length, nodes.Length];

            for (int k = 0; k < nodes.Length; k++)
            {
                for (int i = 0; i < nodes.Length; i++)
                {
                    for (int j = 0; j < nodes.Length; j++)
                    {
                        if (i == j) continue;
                        if ((D[i, k] != int.MaxValue && D[k, j] != int.MaxValue && ((D[i, k] + D[k, j]) < D[i, j])))
                        {
                            D[i, j] = D[i, k] + D[k, j];
                            P[i, j] = nodes[k];
                        }
                    }
                }
            }
        }

        /***** vrátí vzdálenost z Termu(source) do Termu(target) *****/
        public int getShortestDistance(Int32 source, Int32 target)
        {
            return D[getID(source), getID(target)];
        }

        /***** vrátí nejkratší cestu jako pole ID Termů *****/
        public List<Int32> getShortestPath(Int32 sourceID, Int32 targetID)
        {
            Node source = new Node(sourceID);
            Node target = new Node(targetID);
            List<Int32> intPath = new List<Int32>();

            if (D[getID(source.Name), getID(target.Name)] == int.MaxValue)
            {
                return new List<Int32>();
            }
            List<Node> path = getIntermediatePath(source, target);
            intPath.Add(sourceID);
            foreach (Node pathNode in path)
                intPath.Add(pathNode.Name);
            intPath.Add(targetID);
            return intPath;
        }

        /***** vrátí seznam termů mezi source a targetem *****/
        private List<Node> getIntermediatePath(Node source, Node target)
        {
            if (D == null)
            {
                throw new Exception("Must call calcShortestPaths(...) before attempting to obtain a path.");
            }
            if (P[getID(source.Name), getID(target.Name)] == null)
            {
                return new List<Node>();
            }
            List<Node> path = new List<Node>();

            foreach (Node node in getIntermediatePath(source, P[getID(source.Name), getID(target.Name)]))
                path.Add(node); //addAll

            path.Add(P[getID(source.Name), getID(target.Name)]);

            foreach (Node node in getIntermediatePath(P[getID(source.Name), getID(target.Name)], target))
                path.Add(node);//addAll
            return path;
        }

    }

}
